//给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3,1]
//输出：true 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4]
//输出：false 
//
// 示例 3： 
//
// 
//输入：nums = [1,1,1,3,3,4,3,2,4,2]
//输出：true 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// -109 <= nums[i] <= 109 
// 
// Related Topics 数组 哈希表 排序 
// 👍 685 👎 0


import java.util.HashSet;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution217 {
    // 排序然后再判断，时间复杂度O(nlogn + n),比较垃圾算法，推荐使用哈希表时间复杂度O(n),还简单
//    public boolean containsDuplicate(int[] nums) {
//        quickSort(nums, 0, nums.length);
//        for (int i = 0; i < nums.length - 1; i++) {
//            if (nums[i] == nums[i + 1]) {
//                return true;
//            }
//        }
//        return false;
//    }
//
//    // 快速排序，左开右闭
//    private void quickSort(int[] nums, int begin, int end) {
//        if (end - begin < 2) return;
//        int mid = helper(nums, begin, end);
//        quickSort(nums, begin, mid);
//        quickSort(nums, mid + 1, end);
//    }
//
//    private int helper(int[] nums, int begin, int end) {
//        int pivot = nums[begin];
//        end--;
//        while (begin < end) {
//            // <--
//            while (begin < end) {
//                if (nums[end] <= pivot) {
//                    end--;
//                } else {
//                    nums[begin++] = nums[end];
//                    break;
//                }
//            }
//            // -->
//            while (begin < end) {
//                if (nums[begin] >= pivot) {
//                    begin++;
//                } else {
//                    nums[end--] = nums[begin];
//                    break;
//                }
//            }
//        }
//        nums[begin] = pivot;
//        return begin;
//    }
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
